import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * There is a significant amount of repeated code throughout this class
 * due to the resemblance in algorithms solving these problems, 
 * but we had little time to restructure for DRY.
 */
public class SolutionTree {

	private int numInputs;
	private TransitionTable table;

	
	/**
	 * (deprecated)
	 * this method is used to create a solution tree for a machine
	 * @param numInputs number of possible inputs
	 * @param table TransitionTable for the machine
	 * @return SolutionTree object
	 */	
	public static SolutionTree createSolutionTree(int numInputs,
			TransitionTable table) {
		SolutionTree t = new SolutionTree(numInputs, table);
		return t;
	}

	public SolutionTree(int numInputs, TransitionTable table) {
		this.numInputs = numInputs;
		this.table = table;
	}

	/**
	 * @param initState
	 * @param termState
	 * @return a string array of
	 * ALL SHORTEST input sequences that move the machine from initState to termState
	 */
	public String[] solveSCP(String initState, String termState) {
		PriorityQueue<Step> open = new PriorityQueue<Step>();
		HashSet<State> visited = new HashSet<State>();
		ArrayList<Step> solutions = new ArrayList<Step>();

		open.add(new Step("", new State(initState)));

		while (!open.isEmpty()) {
			Step s = open.poll();
			visited.add(s.state);

			if (s.state.equals(termState))
				solutions.add(s);

			for (int i = 0; i < numInputs; i++) {
				State ns = table.getNextState(s.state, i);
				if (ns != null)
					if (!visited.contains(ns)) {
						open.add(new Step(s.sequence + i, ns));
					}
			}
		}

		String[] seq = new String[solutions.size()];
		Iterator<Step> i = solutions.iterator();
		int j = 0;
		while (i.hasNext()) {
			seq[j++] = i.next().sequence;
		}

		return seq;
	}

	/**
	 * @return 2-D String array of ALL solutions ordered based on the length of their input sequence
	 */
	public String[][] solveTSIP() {
		PriorityQueue<Step> open = new PriorityQueue<Step>();
		HashSet<String> visited = new HashSet<String>();
		ArrayList<Step> solutions = new ArrayList<Step>();

		Step init = new Step("");
		init.clusters.put("", new Cluster("", table.getStateSet()));
		open.add(init);

		while (!open.isEmpty()) {
			Step s = open.poll();
			visited.add(s.hashString());

			boolean isSolution = true;

			for (int i = 0; i < numInputs; i++) {
				Step ns = new Step(s.sequence + i);
				Iterator<Cluster> cls = s.clusters.values().iterator();

				while (cls.hasNext()) {
					Cluster cl = cls.next();
					if (cl.size() > 1)
						isSolution = false;
					Iterator<State> states = cl.iterator();
					while (states.hasNext()) {
						State state = states.next();
						State nxtState = table.getNextState(state, i);

						if (ns.clusters
								.containsKey(cl.output + nxtState.output)) {
							if (!ns.clusters.get(cl.output + nxtState.output).states
									.contains(nxtState))
								ns.clusters.get(cl.output + nxtState.output).states
										.add(nxtState);
						} else {
							Cluster n = new Cluster(cl.output + nxtState.output);
							n.states.add(nxtState);
							ns.clusters.put(cl.output + nxtState.output, n);
						}
					}
				}

				if (isSolution) {
					solutions.add(s);
					break;
				}
				if (!visited.contains(ns.hashString()))
					open.add(ns);
			}
		}

		ArrayList<String[]> sol = new ArrayList<String[]>();
		Iterator<Step> i = solutions.iterator();
		while (i.hasNext()) {
			Step st = i.next();
			Iterator<Cluster> j = st.iterator();
			while (j.hasNext()) {
				Cluster c = j.next();
				String[] row = new String[3];
				row[0] = st.sequence;
				row[1] = c.states.toArray()[0].toString();
				row[2] = c.output;
				sol.add(row);
			}
		}
		
		String[][] seq = new String[sol.size()][];
		sol.toArray(seq);
		return seq;
	}


	/**
	 * @return 2-D String array of ALL solutions ordered based on the length of their input sequence
	 */
	public String[][] solveSynchronize() {
		PriorityQueue<Step> open = new PriorityQueue<Step>();
		HashSet<String> visited = new HashSet<String>();
		ArrayList<Step> solutions = new ArrayList<Step>();

		Step init = new Step("");
		init.clusters.put("", new Cluster("", table.getStateSet()));
		open.add(init);

		while (!open.isEmpty()) {
			Step s = open.poll();
			visited.add(s.hashString());

			boolean isSolution = true;

			for (int i = 0; i < numInputs; i++) {
				Step ns = new Step(s.sequence + i);
				Iterator<Cluster> cls = s.clusters.values().iterator();

				while (cls.hasNext()) {
					Cluster cl = cls.next();
					if (cl.size() > 1)
						isSolution = false;
					Iterator<State> states = cl.iterator();
					while (states.hasNext()) {
						State state = states.next();
						State nxtState = table.getNextState(state, i);

						if (!ns.clusters.isEmpty()) {
							if (!ns.clusters.get("").states.contains(nxtState))
								ns.clusters.get("").states.add(nxtState);
						} else {
							Cluster n = new Cluster("");
							n.states.add(nxtState);
							ns.clusters.put("", n);
						}
					}
				}

				if (isSolution) {
					solutions.add(s);
					break;
				}
				if (!visited.contains(ns.hashString()))
					open.add(ns);
			}
		}

		ArrayList<String[]> sol = new ArrayList<String[]>();
		Iterator<Step> i = solutions.iterator();
		while (i.hasNext()) {
			Step st = i.next();
			Iterator<Cluster> j = st.iterator();
			while (j.hasNext()) {
				Cluster c = j.next();
				String[] row = new String[2];
				row[0] = st.sequence;
				row[1] = c.states.toArray()[0].toString();
				sol.add(row);
			}
		}
		
		String[][] seq = new String[sol.size()][];
		sol.toArray(seq);
		return seq;
	}


	/**
	 * @return 2-D String array of ALL solutions ordered based on the length of their input sequence
	 */
	public String[][] solveISIP() {
		PriorityQueue<Step> open = new PriorityQueue<Step>();
		HashSet<String> visited = new HashSet<String>();
		ArrayList<Step> solutions = new ArrayList<Step>();

		Step init = new Step("");
		init.clusters.put("", new Cluster("", table.getStateSet()));
		open.add(init);

		while (!open.isEmpty()) {
			Step s = open.poll();
			visited.add(s.hashString());

			boolean isSolution = true;
			boolean ground = false;

			for (int i = 0; i < numInputs; i++) {
				Step ns = new Step(s.sequence + i);
				Iterator<Cluster> cls = s.clusters.values().iterator();

				while (cls.hasNext()) {
					Cluster cl = cls.next();
					if (cl.size() > 1)
						isSolution = false;
					Iterator<State> states = cl.iterator();
					while (states.hasNext()) {
						State state = states.next();
						State nxtState = table.getNextState(state, i);
						if (state.initName == null)
							nxtState.initName = state.name;
						else
							nxtState.initName = state.initName;

						if (ns.clusters
								.containsKey(cl.output + nxtState.output)) {
							if (!ns.clusters.get(cl.output + nxtState.output).states
									.contains(nxtState)) {
								if (!ns.clusters.get(cl.output
										+ nxtState.output).finals
										.contains(nxtState)) {
									ns.clusters
											.get(cl.output + nxtState.output).states
											.add(nxtState);
									ns.clusters
											.get(cl.output + nxtState.output).finals
											.add(new State(nxtState.name));
								} else {
									ground = true;
								}
							}
						} else {
							Cluster n = new Cluster(cl.output + nxtState.output);
							n.states.add(nxtState);
							ns.clusters.put(cl.output + nxtState.output, n);
						}
					}
				}

				if (isSolution) {
					solutions.add(s);
					break;
				}
				if (!visited.contains(ns.hashString()) && !ground)
					open.add(ns);
			}
		}

		ArrayList<String[]> sol = new ArrayList<String[]>();
		Iterator<Step> i = solutions.iterator();
		while (i.hasNext()) {
			Step st = i.next();
			Iterator<Cluster> j = st.iterator();
			while (j.hasNext()) {
				Cluster c = j.next();
				String[] row = new String[4];
				row[0] = st.sequence;
				row[1] = ((State)c.states.toArray()[0]).initName;
				row[2] = ((State)c.states.toArray()[0]).name;
				row[3] = c.output;
				sol.add(row);
			}
		}
		
		String[][] seq = new String[sol.size()][];
		sol.toArray(seq);
		return seq;
	}

	private class Step implements Comparable<Step>, Iterable<Cluster> {
		String sequence;
		State state;
		private TreeMap<String, Cluster> clusters;

		public Step(String input) {
			sequence = input;
			clusters = new TreeMap<String, Cluster>();
		}

		public Step(String input, State state) {
			this.sequence = input;
			this.state = state;
		}

		public String toString() {
			if (state != null)
				return state.toString();
			else
				return sequence + clusters.toString();
		}

		/**
		 * produces string representation 
		 * resulting from appending the result of .hashString() of all clusters
		 * this string is used in hashing the Step class for uniqueness
		 * this method is valuable for checking if a step has been visited before
		 * @return hash string
		 */
		public String hashString() {
			StringBuilder sb = new StringBuilder();
			Iterator<Cluster> cls = new TreeSet<Cluster>(clusters.values())
					.iterator();
			while (cls.hasNext()) {
				sb.append(cls.next().hashString());
			}
			return sb.toString();
		}

		/**
		 * compares the length of the input sequences that lead to both Steps
		 * this is used for ordering a priority queue of Steps
		 * valuable for obtaining the shortest solutions first 
		 */
		@Override
		public int compareTo(Step o) {
			if (sequence.length() > o.sequence.length())
				return 1;
			else if (sequence.length() == o.sequence.length())
				return 0;
			else
				return -1;
		}

		@Override
		public Iterator<Cluster> iterator() {
			return clusters.values().iterator();
		}

	}

	private class Cluster implements Comparable<Cluster>, Iterable<State> {
		String output;
		HashSet<State> states;
		HashSet<State> finals;

		public Cluster(String output) {
			this.output = output;
			this.states = new HashSet<State>();
			this.finals = new HashSet<State>();
		}

		public Cluster(String output, Collection<State> states) {
			this.output = output;
			this.states = new HashSet<State>(states);
		}

		/**
		 * compares the string representation of the states in the clusters
		 * the Step class maintains an ordered list of clusters
		 * this method is valuable for checking if a step has been visited before
		 */
		@Override
		public int compareTo(Cluster o) {
			return states.toString().compareTo(o.states.toString());
		}

		@Override
		public Iterator<State> iterator() {
			return states.iterator();
		}

		public int size() {
			return states.size();
		}

		/**
		 * returns the string representation of the states in the clusters
		 * this string is used in hashing the Step class for uniqueness
         * this hashing method assumes states are added to the cluster in a specific order.
         * this method is valuable for checking if a step has been visited before
		 * @return hash string
		 */
		public String hashString() {
			return states.toString();
		}

		public String toString() {
			return states.toString() + "/" + output;
		}
	}
}
